package chapterright06;

/**
 * Created by Miracle yaochengwei on 2022/6/19 14:56
 */

public class Homework04 {

    public static void main(String[] args) {

                /*
        已知有个升序的数组，要求插入一个元素，该数组顺序依然是升序，比如:
        [10,12，45,90]，添加23后，数组为[10,12，23,45,90]
        思路本质数组扩容+定位
        1。我们先确定添加数应该插入到哪个
        2.
                 */


        //先定义原数组
        int[] arr = {10, 12, 45, 90};
        int insertNum = 111;
        int index = -1; //index就是要插入的位置

        //遍历 arr数组 如果发现 insertNum<=arr[i], 说明i就是要插入的位置
        //使用 index 保留 index = i;
        // 如果遍历完后，没有发现 insertNum<=arr[i]  说明index = arr.length
        //既：添加到arr的最后

        for(int i = 0; i < arr.length; i++) {
            if(insertNum <= arr[i]) {
                index = i;
                break; //找到位置后，就退出
            }
        }

        //判断index 的值
        if(index == -1) { //说明没有找到位置
            index = arr.length;
        }

        //扩容
        //先创建一个新得数组 大小 arr.length + 1   、、因为要扩容，所以在原来的基础山加1
        int[] arrNew = new int[arr.length + 1];
        //下面老师将arr元素拷贝到 arrNew，并且要跳过index位置
		/*
		分析
		int[] arr = {10, 12, 45, 90};
		arrNew = {              }
		*/
        //i ����arrNew���±�  , j��������arr������±�
        for(int i = 0, j = 0; i < arrNew.length; i++) {

            if( i != index ) { //可以把 arr的元素拷贝到 arrNew
                arrNew[i] = arr[j];
                j++;
            } else { //i这个位置就是要插入的数
                arrNew[i] = insertNum;
            }
        }

        //让arr指向 arrNew , 原来的数组，就成为垃圾，被销毁
        arr = arrNew;

        System.out.println("======插入后arr数组元素的情况======");
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}
